package leetcode_day._2021._202104._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/24 10:35
 * 组合总合 IV
 * 动态规划
 * 01 背包问题
 * 先遍历背包，再遍历物品
 * 因为 1 2 和 2 1 是两种不同的结果
 * dp[i] += dp[i - nums[j]]
 */
public class _24_377 {

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}
